package main

import . "local/algorithm/util"

func mergeKLists(lists []*ListNode) *ListNode {
	if lists == nil {
		return nil
	}

	if len(lists) == 1 {
		return lists[0]
	}

	l := len(lists)
	m := l / 2
	left := mergeKLists(lists[:m])
	right := mergeKLists(lists[m:])
	return mergeLists(left, right)
}

func mergeLists(left, right *ListNode) *ListNode {
	if left == nil {
		return right
	}

	if right == nil {
		return left
	}

	if left.Val < right.Val {
		left.Next = mergeLists(left.Next, right)
		return left
	} else {
		right.Next = mergeLists(left, right.Next)
		return right
	}
}

func main() {

	lists := []*ListNode{
		GenerateLinkedList([]int{1, 3, 5}),
		GenerateLinkedList([]int{2, 4, 6}),
	}
	newList := mergeKLists(lists)
	PrintLinkedList(newList)
}
